import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {

    }
}
/*
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：

    MyCircularQueue(k): 构造器，设置队列长度为 k 。
    Front: 从队首获取元素。如果队列为空，返回 -1 。
    Rear: 获取队尾元素。如果队列为空，返回 -1 。
    enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
    deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
    isEmpty(): 检查循环队列是否为空。
    isFull(): 检查循环队列是否已满。

 */
class MyCircularQueue {
    private int[] array;
    private int left = 0;
    private int right = 0;
    public MyCircularQueue(int k) {
        array = new int[k+1];
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }else {
            array[right] = value;
            right = (right+1) % array.length;
            return true;
        }
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }else {
            left = (left+1) % array.length;
            return true;
        }
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }else {
            return array[left];
        }
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }else{
            if (right == 0)
            {
                return array[array.length - 1];
            }
            return array[right % array.length - 1];
        }
    }

    public boolean isEmpty() {
        if (left == right) {
            return true;
        }else {
            return false;
        }
    }

    public boolean isFull() {
        if (left == (right + 1) % array.length) {
            return true;
        }else {
            return false;
        }
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

/*
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

    void push(int x) 将元素 x 推到队列的末尾
    int pop() 从队列的开头移除并返回元素
    int peek() 返回队列开头的元素
    boolean empty() 如果队列为空，返回 true ；否则，返回 false
 */
class MyQueue2 {
    private Stack<Integer> t1;
    private Stack<Integer> t2;

    public MyQueue2() {
        t1 = new Stack<>();
        t2 = new Stack<>();
    }

    public void push(int x) {
        if (empty()) {
            t1.push(x);
        }else {
            if (t1.isEmpty()) {
                while(!t2.isEmpty()){
                    t1.push(t2.pop());
                }
                t1.push(x);
                while(!t1.isEmpty()) {
                    t2.push(t1.pop());
                }
            }else if (t2.isEmpty()) {
                while(!t1.isEmpty()) {
                    t2.push(t1.pop());
                }
                t2.push(x);
                while(!t2.isEmpty()){
                    t1.push(t2.pop());
                }
            }
        }
    }

    public int pop() {
        if (t1.isEmpty()) {
            return t2.pop();
        }else {
            return t1.pop();
        }
    }

    public int peek() {
        if (t1.isEmpty()) {
            return t2.peek();
        }else {
            return t1.peek();
        }
    }

    public boolean empty() {
        if (t1.isEmpty() && t2.isEmpty()) {
            return true;
        }else {
            return false;
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
/*
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

 */
class MyStack {
    private Queue<Integer> t1;
    private Queue<Integer> t2;
    public MyStack() {
        t1 = new LinkedList();
        t2 = new LinkedList();
    }

    public void push(int x) {
        if (empty()) {
            t1.offer(x);
        }else {
            if (t1.isEmpty()) {
                t1.offer(x);
                while (!t2.isEmpty()) {
                    t1.offer(t2.poll());
                }
            }else if (t2.isEmpty()) {
                t2.offer(x);
                while (!t1.isEmpty()) {
                    t2.offer(t1.poll());
                }
            }
        }
    }

    public int pop() {
        if (t1.isEmpty()){
            return t2.poll();
        }else {
            return t1.poll();
        }
    }

    public int top() {
        if (t1.isEmpty()){
            return t2.peek();
        }else {
            return t1.peek();
        }
    }

    public boolean empty() {
        if(t1.isEmpty() && t2.isEmpty()) {
            return true;
        }else{
            return false;
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
 class MyQueue {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode first;

    public ListNode last;

    /**
     * 入队操作： 尾插法
     *
     * @param val
     */
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (first == null) {
            first = last = node;
        }else {
            node.prev = last;
            last.next = node;
            last = node;
        }

    }

    /**
     * 获取队头元素删除
     *
     * @return
     */
    public int poll() {
        if (first == null) {
            return -1;
        }else {
            int ret = first.val;
            first.next.prev = null;
            first = first.next;
            return ret;
        }
    }
}